/**
 * 1760. 袋子里最少数目的球
 * https://leetcode-cn.com/problems/minimum-limit-of-balls-in-a-bag/
 */
public class Solutions_1760 {
    public static void main(String[] args) {
//        int[] nums = {9};
//        int maxOperations = 2;  // output: 3

//        int[] nums = {2, 4, 8, 2};
//        int maxOperations = 4;  // output: 2

        int[] nums = {7, 17};
        int maxOperations = 2;  // output: 7

        int result = minimumSize(nums, maxOperations);
        System.out.println(result);
    }

    /**
     * 解题思路：二分查找
     * 与 爱吃香蕉的珂珂 题目类似
     * 最小值 1，最大值 max(nums) 为二分查找边界
     * 逐步判断 mid 开销，是否满足 maxOperations 次内将 nums 中的球完成分割
     * 若满足，则 mid 可以尽可能得小，即 right 缩小
     * 若不满足，则 mid 需要更大，即 left 扩大
     *
     * 最终 left，即是最小的且满足条件的值
     */
    public static int minimumSize(int[] nums, int maxOperations) {
        // 找到 nums 中的最大值
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            int need = check(nums, mid);

            // 每个袋子中最多 mid 个球时，nums 中的球需要操作 need 次
            if (need <= maxOperations) {
                // mid 还可以小一点，使开销尽可能更小
                right = mid;
            } else {
                // mid 需要更大点，因为 maxOperations 次内无法完成
                left = mid + 1;
            }
        }
        return left;
    }

    public static int check(int[] nums, int mid) {
        int cnt = 0;
        for (int num : nums) {
            cnt += (num - 1) / mid;
//            cnt += num / mid;
//            if (num % mid != 0) {
//                cnt ++;
//            }
//            cnt --;
        }
        return cnt;
    }
}
